// ****************************************************************
// Copyright 2012, Stephan Burguchev
// e-mail: me@sburg.net
// ****************************************************************
// *
using System;
using System.Collections.Generic;
using System.Linq;
using Version = Updater.Utils.Version;

namespace Updater.Common
{
    /// <summary>
    ///     Complex algorithms required in update process.
    /// </summary>
    public static class Algorithms
    {
        /// <summary>
        ///     Gets the updates sequence from current version to the latest using shortest
        ///     path finding algorithm assuming that all updates have equal cost.
        /// </summary>
        /// <param name="updates">
        ///     The array of available updates.
        /// </param>
        /// <param name="currentVersion">
        ///     Current version of the application.
        /// </param>
        /// <returns>
        ///     A list of updates to update the application to the latest version
        ///     using shortest update sequence.
        /// </returns>
        public static List<UpdateInformation> GetShortestUpdateSequence(
            UpdateInformation[] updates,
            Version currentVersion)
        {
            List<Version> versionsChain;
            return GetShortestUpdateSequence(updates, currentVersion, out versionsChain);
        }

        /// <summary>
        ///     Gets the updates sequence from current version to the latest using shortest
        ///     path finding algorithm assuming that all updates have equal cost.
        /// </summary>
        /// <param name="updates">
        ///     The array of available updates.
        /// </param>
        /// <param name="currentVersion">
        ///     Current version of the application.
        /// </param>
        /// <param name="versionsChain">
        ///     A list of versions containing current, final and intemediate versions
        ///     of the application.
        /// </param>
        /// <returns>
        ///     A list of updates to update the application to the latest version
        ///     using shortest update sequence.
        /// </returns>
        public static List<UpdateInformation> GetShortestUpdateSequence(
            UpdateInformation[] updates,
            Version currentVersion,
            out List<Version> versionsChain)
        {
            versionsChain = new List<Version>();

            // cache = versionTo => (cost, lastPerformedUpdate, versionTheUpdateShouldBeAppliedTo)
            var cache = new Dictionary<Version, System.Tuple<int, UpdateInformation, Version>>();
            cache[currentVersion] = Tuple.Create(0, (UpdateInformation)null, (Version)null);
            IGrouping<Version, UpdateInformation>[] updatesByVersionTo =
                updates.Where(u => u.Version > currentVersion).GroupBy(u => u.Version).ToArray();

            if (updatesByVersionTo.Length == 0)
            {
                // There are no updates found for version currentVersion at all
                return new List<UpdateInformation>();
            }

            foreach (var item in updatesByVersionTo)
            {
                Version versionTo = item.Key;
                Tuple<int, UpdateInformation, Version> result =
                    Tuple.Create(int.MaxValue, (UpdateInformation)null, (Version)null);
                foreach (UpdateInformation updateInfo in item)
                {
                    Tuple<int, UpdateInformation, Version> val;
                    if (updateInfo.MinVersion == null ||
                        updateInfo.MinVersion <= currentVersion)
                    {
                        val = Tuple.Create(1, updateInfo, currentVersion);
                    }
                    else
                    {
                        Version version = null;
                        val = Tuple.Create(int.MaxValue, (UpdateInformation)null, (Version)null);
                        foreach (var pair in cache
                            .Where(e => (e.Key == null || e.Key >= updateInfo.MinVersion) && e.Key < updateInfo.Version)
                            .Select(e => e.Value))
                        {
                            if (val.Item1 >
                                pair.Item1)
                            {
                                val = pair;
                                version = pair.Item2.Version;
                            }
                        }

                        if (val.Item1 ==
                            int.MaxValue)
                        {
                            // There are no updates found to update from version CurrentVersion to updateInfo.Version
                            continue;
                        }

                        val = Tuple.Create(val.Item1 + 1, updateInfo, version);
                    }

                    if (result.Item1 >
                        val.Item1)
                    {
                        result = val;
                    }
                }

                cache[versionTo] = result;
            }

            Version lastVersionTo = cache.LastOrDefault(p => p.Value.Item1 != int.MaxValue).Key;
            if (lastVersionTo == null)
            {
                // There are no updates found to update from current version to any followed version
                return new List<UpdateInformation>();
            }

            var updatesList = new List<UpdateInformation>();
            versionsChain = new List<Version>
                {
                    lastVersionTo
                };
            for (Tuple<int, UpdateInformation, Version> t = cache[lastVersionTo]; t.Item3 != null; t = cache[t.Item3])
            {
                updatesList.Insert(0, t.Item2);
                versionsChain.Insert(0, t.Item3);
            }

            return updatesList;
        }
    }
}
